#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "DataStructures.h"
#include "helperFuncs.h"

#define MAX_LINE_SIZE 64 // assuming max line size is 64: max integer length * 3... and some...

typedef struct {
	Queue * queues; //input queues
	List requests; //List of match requests
	List grants; //List of grants
	int grant_round_robin; //current highest priority port number for grant decision
	int accept_round_robin; //current highest priority port number for accept decision
	int input_locked; //flag that indicates that some other port was matched to send data to this port in current step
	int output_locked; //flag that indicates that this port was matched ot send data to some other port in current step
} Port; //struct that represents a port in a network switch

typedef struct {
	int num_ports; //number of ports in the switch
	Port * ports; // array of ports
	int awaiting_packets; //number of packets that currently waiting for output
	Queue output_packets; //packets that were sent to output in current time step. 
	//The implementation by queue doesn't represent the real word where packets go to output in parallel,
	//but it is convenient to print the packets in a specific order.
} NetworkSwitch; //struct that represents a network switch

typedef struct {
	int num_ports; //number of ports that should be in network switch
	int k; //number of iSlip iterations to perform every time step
	int r; //run index (for log file name)
	int cur_step; //current time step that being performed
	int cur_islip_iteration; //current iSlip iteration that being perfomed
	int cur_line; //last line number that read from stdin
	Packet packet_buffer; //used to store packet that read from input
	int awaiting_packet_buffer; //indicates that there is a packet that was read in previous step but should handle it now
	FILE * log_file; //pointer to log file
	int resume_fetch_packets; //flag that indicates if there are more packets to read from input
} SchedulerParameters; //struct used to hold scheduler parameters that read from command line and also parameters used in run time

/*Reads command line parameters and verifies them, and stores them in scheduler_parameters. Also initializes other fields in this struct*/
int readAndVerifySchedulerParameters(SchedulerParameters * scheduler_parameters, int argc, char * argv[]); 

/* Initializes network_switch variable that used to represent the network switch that is being simulated */
int initNetworkSwitch(SchedulerParameters * scheduler_parameters, NetworkSwitch * network_switch);

/* Performs a single time step of the scheduler that includes running iSlip, fetching new packets, outputing matched packets */
int performTimeStep(SchedulerParameters * scheduler_parameters, NetworkSwitch * network_switch);

/*Creates a new packet with given data and pushes it to input queue*/
int pushPacketToInputQueue(NetworkSwitch * network_switch, Packet * packet);

/* Fetches a packet line from the input and parses it */
int fetchLine(char * line, int * arrival_time, int * arrival_port, int * destination_port);

/* Reads all the packets of the given step from input and puts them in queues */
int fetchPackets(SchedulerParameters * scheduler_parameters, NetworkSwitch * network_switch);

/* Performs iSlip algorithm on the switch for k iterations*/
void iSlip(SchedulerParameters * scheduler_parameters, NetworkSwitch * network_switch);

/* Performs a single iteration of the iSlip algorithm */
void iSlipIteration(SchedulerParameters * scheduler_parameters, NetworkSwitch * network_switch);

/* Performs the Request step of the iSlip algorithm */
void iSlipRequest(SchedulerParameters * scheduler_parameters, NetworkSwitch * network_switch);

/* Performs the Grant step of the iSlip algorithm */
void iSlipGrant(SchedulerParameters * scheduler_parameters, NetworkSwitch * network_switch);

/* Performs the Accept step of the iSlip algorithm, also removing matched packet from relevant queues and sends them to output */
void iSlipAccept(SchedulerParameters * scheduler_parameters, NetworkSwitch * network_switch);

/** used for debugging iSlip algorithm**/
void iSlipPrint(SchedulerParameters * scheduler_parameters, NetworkSwitch * network_switch);

/* Prints a line that represents packet departure within the given format*/
void outputPacketLine(int arrivale_time, int arrival_port, int destination_port, int leave_time);

/* Prints all the packets that sent to output after iSlip algorithm*/
void outputPackets(SchedulerParameters * scheduler_parameters, NetworkSwitch * network_switch);

/* Creates a log file for current run*/
int openLogFile(SchedulerParameters * scheduler_parameters);

/* Writes info into log for current step in the given format */
void writeToLog(SchedulerParameters * scheduler_parameters, NetworkSwitch * network_switch);

/* Frees all the memory that allocated on heap */
void freeAll(SchedulerParameters * scheduler_parameters, NetworkSwitch * network_switch);

/** Used for debugging - prints queues**/
void printAll(SchedulerParameters * scheduler_parameters, NetworkSwitch * network_switch);

int readAndVerifySchedulerParameters(SchedulerParameters * scheduler_parameters, int argc, char * argv[]) {

	if (argc != 4) { /* program needs to get 3 parameters */
		fprintf(stderr,"Error : input must include 3 parameters:\nislip N k r\n");
		return 0;
	}

	if (!isNumeric(argv[1],&scheduler_parameters->num_ports)) {
		fprintf(stderr,"Error : invalid switch dimension (N)!\n");
		return 0;
	}

	if (!isNumeric(argv[2],&scheduler_parameters->k)) {
		fprintf(stderr,"Error : invalid number of iSlip iterations (k)!\n");
		return 0;
	}

	if (!isNumeric(argv[3],&scheduler_parameters->r)) {
		fprintf(stderr,"Error : invalid run number (r)!\n");
		return 0;
	}

	//initialize scheduler parameters that used in run time
	scheduler_parameters->cur_step = 1; // Initialize current time step to 1 (we start counting from 1)
	scheduler_parameters->awaiting_packet_buffer = 0;
	scheduler_parameters->resume_fetch_packets = 1;
	scheduler_parameters->cur_line = 0;

	//init packet buffer
	scheduler_parameters->packet_buffer.arrival_port = -1;
	scheduler_parameters->packet_buffer.arrival_time = -1;
	scheduler_parameters->packet_buffer.destination_port = -1;
	scheduler_parameters->packet_buffer.leave_time = -1;
	scheduler_parameters->packet_buffer.next = NULL;

	return 1;
}

int initNetworkSwitch(SchedulerParameters * scheduler_parameters, NetworkSwitch * network_switch) {
	int i, N;

	N = scheduler_parameters->num_ports; //use local var for simplier syntax
	network_switch->num_ports = N; //assign to switch the number of ports that read from command line

	network_switch->ports = (Port *)malloc((N)*sizeof(Port)); //alocate memory for ports
	if (network_switch->ports == NULL)
		return 0; //failed to allocate memory, should terminate.

	//iterate over all ports
	for (i = 0 ; i < N; i++) {

		network_switch->ports[i].queues = (Queue *)malloc(N*sizeof(Queue)); //allocate memory for queues
		if (network_switch->ports[i].queues == NULL)
			return 0; //failed to allocate memory, should terminate.

		initQueues(network_switch->ports[i].queues, N); //initialize the queues

		initList(&network_switch->ports[i].requests); //initialize list used for iSlip requests
		initList(&network_switch->ports[i].grants); //initialize list used for iSlip grants

		network_switch->ports[i].grant_round_robin = 0; //Initialize highest priority port for grant decision to port0
		network_switch->ports[i].accept_round_robin = 0; //Initialize highest priority port for accept decision to port0

		network_switch->ports[i].input_locked = 0; //initially the port is not matched
		network_switch->ports[i].output_locked = 0;//initially the port is not matched
	}

	initQueue(&network_switch->output_packets); //initialize the output queue
	network_switch->awaiting_packets = 0; // in the beginning there are no packets in the switch

	return 1;
}

int performTimeStep(SchedulerParameters * scheduler_parameters, NetworkSwitch * network_switch) {

	int result;
	if (network_switch->awaiting_packets > 0) {//at the beginning of the step, perform matchings using iSlip, if there are awaiting packets
		iSlip(scheduler_parameters, network_switch); 
		outputPackets(scheduler_parameters, network_switch); //print packets that were sent to output
		destroyQueue(&network_switch->output_packets);
	}

	if (scheduler_parameters->resume_fetch_packets) //if there are more packets at input, get them
		if (fetchPackets(scheduler_parameters, network_switch) == 0)
			return 0; // fetching packets failed, should terminate

	writeToLog(scheduler_parameters, network_switch); //write buffers' status to the log

	return 1;
}

int pushPacketToInputQueue(NetworkSwitch * network_switch, Packet * packet) {

	Packet * tmp_packet;

	tmp_packet = (Packet *)malloc(sizeof(Packet));
	if (tmp_packet == NULL)
		return 0; //failed to allocate memory

	*tmp_packet = *packet; //copy data
	insertToQueue(&network_switch->ports[packet->arrival_port].queues[packet->destination_port], tmp_packet);
	network_switch->awaiting_packets = network_switch->awaiting_packets + 1;

	return 1;
}

int fetchLine(char * line, int * arrival_time, int * arrival_port, int * destination_port) {
	if (!(isNumeric(strtok(line," "),arrival_time))) { //arrival time should be a positive number
		fprintf(stderr,"Error : invalid arrival time ");
		return 0;
	}

	if (!(isNumeric(strtok(NULL," "),arrival_port))) { //arrival port should be a positive number
		fprintf(stderr,"Error : invalid arrival port ");
		return 0;
	}

	if (!(isNumeric(strtok(NULL," "),destination_port))) { //destination port should be a positive number
		fprintf(stderr,"Error : invalid destination port ");
		return 0;
	}

	return 1;
}

int fetchPackets(SchedulerParameters * scheduler_parameters, NetworkSwitch * network_switch) {
	char line[MAX_LINE_SIZE];

	Packet * packet_buffer = &(scheduler_parameters->packet_buffer);

	int N = network_switch->num_ports;
	Port * ports = network_switch->ports;

	//there is awaiting packet from previous step
	if (scheduler_parameters->awaiting_packet_buffer && (packet_buffer->arrival_time == scheduler_parameters->cur_step)) {
		if (!pushPacketToInputQueue(network_switch, packet_buffer)) {
			fprintf(stderr,"Failed pushing packet to queue, line #%d. Program should terminate\n", scheduler_parameters->cur_line);
			return 0;
		}
	}
	scheduler_parameters->awaiting_packet_buffer = 0;
	scheduler_parameters->resume_fetch_packets = 0; // assuming packets will be fetched till end of stdin

	while(fgets(line, MAX_LINE_SIZE, stdin) != NULL) {
		if (trimWhiteSpace(line)[0] == '\0')
			continue; //skip empty lines

		if (!fetchLine(line, &(packet_buffer->arrival_time), &(packet_buffer->arrival_port), &(packet_buffer->destination_port))) {
			fprintf(stderr,"couldn't read packet, in line %d, skipping this line\n",scheduler_parameters->cur_line);
			continue; //error in reading line, skipping
		}

		if (packet_buffer->arrival_port > network_switch->num_ports || packet_buffer->destination_port>network_switch->num_ports)
			//If we get a packet that contains out-of-bounds port value, we ignore it
			continue;

		if (packet_buffer->arrival_time > scheduler_parameters->cur_step){
			//read a packet that belongs to next time step
			scheduler_parameters->awaiting_packet_buffer = 1;
			scheduler_parameters->resume_fetch_packets = 1;
			break;
		};

		if (!pushPacketToInputQueue(network_switch, packet_buffer)) //push packet to relevant queue
		{
			fprintf(stderr,"Failed pushing packet to queue, line #%d. Program should terminate\n", scheduler_parameters->cur_line);
			return 0; //couldn't push packet to queue - general failure
		}

		scheduler_parameters->cur_line = scheduler_parameters->cur_line + 1;
	}

	return 1;
}

void iSlip(SchedulerParameters * scheduler_parameters, NetworkSwitch * network_switch) {
	int i;
	int N = network_switch->num_ports;
	Port * ports = network_switch->ports; //use local pointer for simplier syntax

	//mark all ports as unmatched for both directions
	for (i = 0; i < N; i++) {
		ports[i].input_locked = 0;
		ports[i].output_locked = 0;
	}

	//perform k iterations of iSlip algorithm
	for (i = 0; i < scheduler_parameters->k; i++) {
		scheduler_parameters->cur_islip_iteration = i;
		iSlipIteration(scheduler_parameters, network_switch);
	}
}

void iSlipIteration(SchedulerParameters * scheduler_parameters, NetworkSwitch * network_switch) {

	int i;
	int N = network_switch->num_ports;
	Port * ports = network_switch->ports;

	//perform 3 steps of the algorithm
	iSlipRequest(scheduler_parameters, network_switch);
	iSlipGrant(scheduler_parameters, network_switch);
	iSlipAccept(scheduler_parameters, network_switch);

	//clear the lists of requests and grants at the end of the iteration
	for (i = 0; i < N; i++) {
		destroyList(&ports[i].requests);
		destroyList(&ports[i].grants);
	}
}

void iSlipRequest(SchedulerParameters * scheduler_parameters, NetworkSwitch * network_switch) {
	int i, j;
	int N = network_switch->num_ports;
	Port * ports = network_switch->ports;

	//iterate over input ports
	for (i = 0; i < N; i++) {
		if (ports[i].output_locked == 1) //if the output from this port already matched, skip it
			continue;
		//iterate over output ports
		for (j = 0; j < N; j++) {
			if (ports[j].input_locked == 1) //if the input to this port already matched, skip it
				continue;
			if (ports[i].queues[j].size > 0) { //if there is awaiting packet: port_i --> port_j, add port_i to requests list of port_j
				pushBack(&ports[j].requests, i);
			}
		}
	}
}

void iSlipGrant(SchedulerParameters * scheduler_parameters, NetworkSwitch * network_switch) {
	int i;
	List * pList;
	ListNode * pNode;
	int grant;

	int N = network_switch->num_ports;
	Port * ports = network_switch->ports;

	//iterate over output ports
	for (i = 0; i < N; i++) {

		pList = &ports[i].requests;
		if (pList->size == 0) //if no requests for this port, skip it
			continue;

		pNode = pList->head;

		/*Initially, grant the first requested port.
		Since the requests are in sorted rising order (the list defenitely was built in such order),
		if there is a request with port number larger or equals the round robin pointer, it will be detected and reassigned.
		Otherwise, it should be exactly the lowest port number in the list  */
		grant = pNode->val; 
		while (pNode != NULL) { 
			if (pNode->val >= ports[i].grant_round_robin) {
				grant = pNode->val;
				break;
			}
			pNode = pNode->next;
		}	
		pushBack(&ports[grant].grants, i); //add the port_#i number to list of grants of the chosen port_#grant
	}
}

void iSlipAccept(SchedulerParameters * scheduler_parameters, NetworkSwitch * network_switch) {

	int i, accept;
	List * pList;
	ListNode * pNode;
	Packet * pPacket;

	int N = network_switch->num_ports;
	Port * ports = network_switch->ports;

	//iterate over input ports
	for (i = 0; i < N; i++) {
		pList = &ports[i].grants;
		if (pList->size == 0) //if no grants for this port, skip it
			continue;
		pNode = pList->head;

		/*Initially, accept the first granted port.
		Since the grants are in sorted rising order (the list defenitely was built in such order),
		if there is a grant with port number larger or equals the round robin pointer, it will be detected and reassigned.
		Otherwise, it should be exactly the lowest port number in the list  */
		accept = pNode->val;
		while (pNode != NULL) {
			if (pNode->val >= ports[i].accept_round_robin) {
				accept = pNode->val;
				break;
			}
			pNode = pNode->next;
		}

		//perform matching: port_#i --> port_#accept
		ports[i].output_locked = 1;
		ports[accept].input_locked = 1; 


		//remove packet from the port_#i-->port_#accept queue 
		pPacket = popQueue(&ports[i].queues[accept]);

		//save the departure time and sent this packet to output
		pPacket->leave_time = scheduler_parameters->cur_step;
		insertToQueue(&network_switch->output_packets, pPacket);
		network_switch->awaiting_packets = network_switch->awaiting_packets - 1;

		/* advance round robin pointer
		By the defenition, round robin pointer should advance iff there was matching in the first iteration of iSlip
		*/
		if (scheduler_parameters->cur_islip_iteration == 0) { 
			ports[i].accept_round_robin = (accept + 1) % N;
			ports[accept].grant_round_robin = (i + 1) % N;
		}

	}
}

void outputPacketLine(int arrivale_time, int arrival_port, int destination_port, int leave_time) {
	fprintf(stdout, "%d %d %d %d\n", arrivale_time, arrival_port, destination_port, leave_time);
}

void outputPackets(SchedulerParameters * scheduler_parameters, NetworkSwitch * network_switch) {

	int i;

	Packet * pPacket = network_switch->output_packets.head;
	//iterate over the output queue and output each packet
	while (pPacket != NULL) {
		outputPacketLine(pPacket->arrival_time, pPacket->arrival_port, pPacket->destination_port, pPacket->leave_time);
		pPacket = pPacket->next;
	}

}

int openLogFile(SchedulerParameters * scheduler_parameters) {
	char log_file_name[15]; // size of file name = max integer length + ".log"

	sprintf(log_file_name,"%d.log",scheduler_parameters->r); //build log name using the run id parameter
	scheduler_parameters->log_file = fopen(log_file_name,"w");
	if (scheduler_parameters->log_file == NULL) {
		fprintf(stderr,"Error : could not open log file\n ");
		return 0;
	}

	return 1;
}

void writeToLog(SchedulerParameters * scheduler_parameters, NetworkSwitch * network_switch) {
	int i,j;

	//iterate over input ports
	for (i = 0 ; i < network_switch->num_ports ; i++)
		//iterate over input queues
		for (j = 0 ; j < network_switch->num_ports ; j++)
			//write the queue size to log
			fprintf(scheduler_parameters->log_file,"%d %d %d %d\n",scheduler_parameters->cur_step,i,j,network_switch->ports[i].queues[j].size);
}

void freeAll(SchedulerParameters * scheduler_parameters, NetworkSwitch * network_switch) {
	int i, j;
	Packet * tmp;

	int N = network_switch->num_ports;
	Port * ports = network_switch->ports;
	if (ports != NULL) {
		for (i = 0; i < N; i++) {
			if (ports[i].queues != NULL) {
				for (j = 0; j < N; j++) {
					if (&ports[i].queues[j] != NULL)
						destroyQueue(&ports[i].queues[j]);
				}
				free(network_switch->ports[i].queues);
			}
			destroyList(&ports[i].requests);
			destroyList(&ports[i].grants);
		}
		free(ports);
		destroyQueue(&network_switch->output_packets);
	}

	if (scheduler_parameters->log_file != NULL)
		fclose(scheduler_parameters->log_file);
}

int main (int argc, char* argv[]) {

	int i;

	SchedulerParameters scheduler_parameters; //Parameters of current scheduler
	NetworkSwitch network_switch; //The sumulated network switch

	//init pointers
	scheduler_parameters.log_file = NULL;
	network_switch.ports = NULL;

	//Read arguments and initialize scheduler parameters
	if (!readAndVerifySchedulerParameters(&scheduler_parameters, argc, argv))
	{
		freeAll(&scheduler_parameters, &network_switch);
		fprintf(stderr, "Failed to assign scheduler parameters\n");
		exit(EXIT_FAILURE);
	}

	//Initialize network_switch
	if (!initNetworkSwitch(&scheduler_parameters, &network_switch))
	{
		freeAll(&scheduler_parameters, &network_switch);
		fprintf(stderr, "Failed to initialize internal data. Probably memory allocation failure\n");
		exit(EXIT_FAILURE);
	}

	if (!openLogFile(&scheduler_parameters)) {
		freeAll(&scheduler_parameters, &network_switch);
		fprintf(stderr, "Failed to open log file\n");
		exit(EXIT_FAILURE);
	}

	//Perform time steps while there are incoming packets or there are packets waiting for output
	while ((scheduler_parameters.resume_fetch_packets == 1) || (network_switch.awaiting_packets != 0)) {
		if (!performTimeStep(&scheduler_parameters, &network_switch))
		{
			freeAll(&scheduler_parameters, &network_switch);
			fprintf(stderr, "Failure while running the scheduler, time step #$d\n", scheduler_parameters.cur_step);
			exit(EXIT_FAILURE);
		}
		scheduler_parameters.cur_step = scheduler_parameters.cur_step + 1;
	}

	//Finish the scheduler.
	freeAll(&scheduler_parameters, &network_switch);

	exit(0);
}


/****** For debug purposes *****/


void iSlipPrint(SchedulerParameters * scheduler_parameters, NetworkSwitch * network_switch) {
	int i;
	int j = 0;
	ListNode * pNode;

	int N = network_switch->num_ports;
	Port * ports = network_switch->ports;

	printf("iSlipPrint step=%d it=%d\n\n", scheduler_parameters->cur_step, scheduler_parameters->cur_islip_iteration);

	for (i = 0; i < N; i++) {
		printf("port#%d requests: ", i);
		pNode = ports[i].requests.head;
		while (pNode != NULL) {
			printf("%d ", pNode->val);
			pNode = pNode->next;
			j++;
		}
		printf("\n");
	}
	printf("\ntotal=%d\n", j);
	j = 0;
	for (i = 0; i < N; i++) {
		printf("port#%d grants: ", i);
		pNode = ports[i].grants.head;
		while (pNode != NULL) {
			printf("%d ", pNode->val);
			pNode = pNode->next;
			j++;
		}
		printf("\n");
	}
	printf("\ntotal=%d\n", j);
}

void printAll(SchedulerParameters * scheduler_parameters, NetworkSwitch * network_switch) {
	int i, j, tot = 0;
	int N = network_switch->num_ports;
	Port * ports = network_switch->ports;
	Packet * pPacket = (Packet *)malloc(sizeof(Packet));
	for (i = 0; i < network_switch->num_ports ; i++) {
		for (j = 0; j < N; j++) {
			if (network_switch->ports[i].queues[j].size == 0)
				continue;
			printf("Queue %d/%d:\n",i,j);
			printf("Size: %d\n",ports[i].queues[j].size);
			pPacket = ports[i].queues[j].head;
			while(pPacket != NULL) {
				printf("%d %d %d\n",pPacket->arrival_time,pPacket->arrival_port,pPacket->destination_port);
				pPacket = pPacket->next;
				tot++;
			}
		}
	}

	printf("total packet: %d\n",tot);
}